A rangefinder is a device for measuring the range from the device to some physical surface. A laser rangefinder can be one of many known types of rangefinders. Laser rangefinders are sometimes known as LIDAR (Light Detection and Ranging) or LADAR (Laser Detection and Ranging) systems. Laser rangefinders use a variety of techniques to measure the range from the apparatus to a surface from which the laser beam is reflected. A typical apparatus may in some manner measure the round trip time-of-flight of the beam from the apparatus's emitter to the target, or the reflector, and back to the apparatus's receiver. One such apparatus is generally commercially available from Acuity Research and known as the AR4000 laser rangefinder, which can be found at URL http://www.acuityresearch.com, for example. Information on example laser rangefinder technology can be found in U.S. Pat. No. 5,309,212 which describes establishing an oscillator whose frequency is dependent on the time-of-flight of the laser beam and then measuring the time period of that oscillator. Since the speed of light is known, this time period measurement can then be readily converted to indicate the range from the apparatus to a surface that reflects the laser beam. A digital interface to a computer is typically included in such rangefinders. Other examples of laser and other rangefinders can be found in the text “Sensors for Mobile Robots: Theory and Application” by H. R. Everett (A. K. Peters, Ltd., 1995).
A rangefinder's laser beam may be directed in various directions by physically pointing the apparatus, by using one or more moving mirrors or prisms under manual or computer control, or both. A common configuration scans the beam in one plane and is called a line scanner, such as that sold commercially by Acuity Research and found at their website, for example. This apparatus includes a laser rangefinder that directs the beam end-on toward a rotating 45-degree mirror. The beam is thus turned at 90 degrees and sweeps out an arc as the 45-degree mirror rotates. The resulting data is a set of range data points representing the profile of an object or space. For example, if the scanned beam is directed at an automobile, a set of data points representing a profile of the automobile is produced.
The rangefinder's laser beam may also be directed to scan in two dimensions by physically pointing the apparatus, by using one or more moving mirrors or prisms, or both. As such the rangefinder's laser beam can thus acquire range measurements to a host of points within the environment. This type of apparatus is sometimes referred to as a scanning 3D laser rangefinder or just scanning laser rangefinder. In general, the three dimensions comprise two dimensions of scanning, such as X and Y, plus range or distance between the rangefinder and a point in space at which the laser beam is directed.
In order to acquire the range measurements to multiple points within an area, the rangefinder beam may be steered under manual or computer control. The steering may be accomplished directly through physical movement or optically through the use of mirrors or prisms. A scanning laser rangefinder sweeps the beam in two directions to cover an area. For example, a scanning laser rangefinder developed by Cyra Technologies Inc. sweeps the beam in an X, Y raster pattern through the use of mirrors. Information on the Cyra rangefinder technology is disclosed in U.S. Pat. No. 5,988,862. As a further example, we discuss the DeltaSphere 3000 laser scanner, such as 100 shown in FIG. 1. As seen, the laser scanner mounts on a tripod 105, includes a laser rangefinder 140, and is controlled by an embedded computer 150. The laser scanner sweeps the laser beam 110 in elevation using a rotating 45-degree mirror 120 and in azimuth by rotating 130 the laser and mirror assembly. Information on the DeltaSphere 3000 laser scanner product can be found at URL http://www.deltasphere.com. Further background on the technology for the DeltaSphere 3000 laser scanner can be found in “Capturing, Processing and Rendering Real-World Scenes”, Videometrics and Optical Methods for 3D Shape Measurement, Electronic Imaging 2001, Photonics West, SPEI Vol. 4309 Jan. 22, 2001, an article by Lars Nyland, Anselmo Lastra, David K. McAllister, Voicu Popescu, and Chris McCue.
Other examples of scanning laser rangefinders can be found in “Sensors for Mobile Robots: Theory and Application” by H. R. Everett (A. K. Peters, Ltd., 1995). The results of these scans are 3D data sets sometimes referred to as “3D point clouds”. Similar data is provided by a rangefinder array design, such as those made commercially by Canesta Inc., also known as a range camera, that enables measurement of multiple range points at once. Information may be found at URL http://www.canesta.com/.
Various 3D rangefinder technologies may collect data at various rates ranging from 1 sample per second to several hundred thousand samples per second, but all provide essentially the same results, an array of 3D points where at least the range, elevation, and azimuth for each point is known. This representation in spherical coordinates may easily be transformed to X, Y, Z values in Cartesian coordinates. The rate of collecting the data points determines the time required to capture the data in the field, but obviously has no impact on later processing and use of the data. It will be clear that the methods discussed in this invention are independent of the speed of capture of the original data and that the methods apply to all forms of 3D rangefinder devices.
3D data sets collected by a 3D rangefinder may be presented as a visual display to a user in several different ways. The visualization techniques fall broadly into two classes, 3D displayed images and 2D displayed images.
A 3D displayed image format is one in which the user may select a particular 3D viewpoint and then view the 3D range data as geometric figures in perspective projection or in orthogonal projection or via some other projection within a 2D computer image. Techniques for creating 3D displayed images are well known from computer graphics textbooks such as “Computer Graphics: Principles and Practice in C” by James D. Foley, Andries van Dam, Steven K. Feiner, and John F. Hughes (Addison Wesley 1995). Well-known formats for a 3D displayed image may have the 3D range data samples represented as 3D points (also known as a point cloud) in which the same color is assigned to all points, in which false color is assigned to each point based on its range, in which color is assigned to each point based on its reflectance intensity (strength of the signal returned from a surface to the 3D rangefinder), or in which points are colored via any other scheme. In another well-known 3D display technique, the 3D range data points may be linked together into a 3D mesh using well known computer graphics techniques, such that neighboring points are connected via lines within the display. The lines of the mesh may be colored using any of the techniques discussed above using well-known computer graphics techniques. In another 3D display technique, the 3D range data points may be linked together into a surface using well known computer graphics techniques. The surface may have range values interpolated between actual data points using linear, quadratic, cubic, or any well-known surface interpolation technique. The color of the surface at each displayed pixel may be determined in any of a number of well-known ways, including computing simulated lighting effects based on the orientation of the interpolated surface, interpolating reflectance intensity values measured at each data point, mapping a 2D image or any other function to the 3D surface using well-known texture-mapping techniques, combinations thereof, or any using other well-known techniques for surface rendering.
A 2D displayed image is one in which the 3D range data set is inherently represented as a 2D image. There are several well-known techniques for creating 2D displayed images since the data from a typical 3D rangefinder is obtained by scanning in two dimensions, typically azimuth and elevation. The resulting data can naturally be represented as a 2D image in spherical projection, where the azimuth angle of a 3D sample is represented as the horizontal or X axis and the elevation angle is represented as vertical or Y axis on the display, and each pixel represents one or more 3D data points depending on the scale chosen. Of course, the 2D displayed image need not be represented in spherical projection, but in any other well-known projection of a 3D data set to a 2D display. As illustrated in FIG. 2, for example, each pixel may have a multiplicity of associated values stored with it, including precise azimuth angle value 210, precise elevation angle value 220, range value 230, reflectance value 240, color 250 (RGB), and any other useful values 260. For example, a useful value might be some other attribute associated with the pixel. The color of each pixel within the 2D displayed image may be determined in any of a number of well-known formats. A Range Image has a false color assigned to each pixel based on its range. A Reflectance Image has a color assigned to each pixel based on the intensity of the reflected laser beam. A Registered Color Image has a color assigned to each pixel based on the color obtained from a color sensor such as a 2D digital camera such that the range data and color data are aligned as shown in FIG. 3. A Registered Color Image may typically be created by the steps of capturing a 3D range data set with a 3D rangefinder and displaying it as a Reflectance Image 310, capturing a 2D image using a calibrated digital color camera and displaying it as a 2D color image 320, identifying corresponding features between the two 2D images such as 311 and 321, 312 and 322, 313 and 323, and 314 and 324, using the locations of the corresponding features to compute the pose (location and orientation) of the 2D digital color camera, using the camera pose information to compute the optical path from the camera into the 3D data set, and applying the color from each pixel of the 2D color image to corresponding points of the 3D data set displayed as a 2D image. Using this method, the 3D range data and 2D color image need not have been acquired from the same viewpoint. Further information on the mathematics underlying the 2D image registration process may be found in an article by R. Y. Tsai, “An Efficient and Accurate Camera Calibration Technique for 3D Machine Vision”, Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Miami Beach, Fla., pp. 364-374, 1986.
Examples of a Range Image, a Reflectance Image, and a Registered Color Image may be found in an article by Lars Nyland, Anselmo Lastra, David K. McAllister, Voicu Popescu, and Chris McCue, titled “Capturing, Processing and Rendering Real-World Scenes”, Videometrics and Optical Methods for 3D Shape Measurement, Electronic Imaging 2001, Photonics West, SPIE Vol. 4309 Jan. 22, 2001. The ability to create and display a Range Image, a Reflectance Image, and a Registered Color Image has been available in the DsControl, DsColor, and other software provided to DeltaSphere 3000 customers beginning some time ago.
When the 3D data set is displayed in any of the above formats, it is a well-known technique for a user to interactively select a particular pixel on the screen and to determine the X, Y, Z coordinates of the data represented at that pixel. In 2D displayed images, for example, the ability to select and display the X, Y, Z coordinates for any point in a Range Image, a Reflectance Image, and a Registered Color Image has been available in the DsControl and other software provided to DeltaSphere 3000 customers beginning some time ago. For 3D displayed images, commonly used computer graphics and computer-aided design software packages have enabled a user to pick a point, a point on a mesh, or a point on a surface and determine the X, Y, Z coordinates of that point. As another example, U.S. Pat. No. 6,922,234 discloses methods of making measurements within a reflectance image obtained from a laser scanner which captures data at up to 125,000 points per second.
It has been common practice for software packages to allow the user to make physical measurements within a 3D range data set, such as specifying data points on two surfaces, calculating the distance between them, and displaying a measurement line between those two data points. For example, this capability has been provided to DeltaSphere customers since some time ago. Other software packages, such as Cyclone from Cyra Technologies for example, have allowed users to fit geometric structures such as cylinders to 3D range data of pipes in a petrochemical plant and to subsequently view these cylinders in Computer Aided Design (CAD) software for visualization and planning. In conventional methods, techniques such as measurement and fitting of structures involve representation of physical entities. For example, the measurement represents distance between physical surfaces within the environment and the cylinders represent physical pipes.
There is, however, another class of calculated geometric entities separate from geometric entities representing actual physical structures. This additional class includes vectors, surfaces, and volumes representing non-physical entities, such as calculated points of origin, calculated paths of motion, calculated regions of fluid flow, and calculated swept volumes. Such calculated geometric entities are distinct in that they represent abstract, not physical structures. In conventional practice these calculated geometric entities may be displayed using well-known 3D graphics techniques and publications in the field of scientific visualization such as “Scientific Visualization: Overviews, Methodologies, and Techniques” by Gregory M. Nielson, Hans Hagen, and Heinrich Mueller (IEEE Computer Society 1997) are very much concerned with such techniques.
For example, the trajectory of a projectile is a calculated vector representing where the projectile might have traveled during a particular time, not a physical representation of the projectile itself. For another example, the origin of an explosion is a calculated point in space, not the physical explosive material. For instance, the line-of-sight of a person who might have been standing at a particular location is not a physical representation of the person's eyes, but a calculated reconstruction of the path along which objects would have been visible to the person. As another example, the area of the floor over which it is calculated a liquid would flow if a certain amount were poured from a particular height is a calculated surface and not a physical representation of the liquid. For example, the volume swept out by a person's path through a room is not a representation of the person, but of all the space throughout which the person's body moved. All of these are examples of calculated geometric entities and it should be readily apparent that there are a host of other useful examples of this class.
It would be advantageous in many applications, particularly in the reconstruction of crime, accident, and terrorism scenes, to be able to specify and display these forms of calculated geometric entities integrated with the 3D data representing an actual physical scene acquired using a 3D rangefinder. As such, the understanding, analysis, and presentation of what occurred at a scene would be greatly enhanced and new applications for 3D rangefinder technology could be enabled.